/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 迷宫问题;


/**
 * @Description 回溯算法经典应用
 * 说明:
 * 小球得到的路径，和程序员设置的找路策略有关即：找路的上下左右的顺序相关
 * 再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化
 * 测试回溯现象
 * <p>
 * 使用二维数组实现
 * 思考: 如何求出最短路径?
 * 通过制定更好的策略！
 * @Author 俊昭
 * @Date 2022/4/29
 */
public class Labyrinth {
    private static int[][] map = new int[8][7];

    static {
        // 模拟墙 值为1是墙
        // 上下
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        // 左右
        for (int i = 1; i < 7; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        // 再设置两块墙
        map[3][1] = 1;
        map[3][2] = 1;
        // 设置一个回溯的条件
//        map[1][2] = 1;
//        map[2][2] = 1;

        // 设置一个复杂点的迷宫
//        map[5][3] = 1;
//        map[5][4] = 1;
//        map[5][5] = 1;


    }

    /**
     * @param x 行坐标
     * @param y 列坐标
     * @return 小球到达 [6][5]即找到
     * @description 寻路
     * 1是墙 2为通路 3为走过但不同
     * 策略：下 右 上 左，走不通再回溯
     * @author 俊昭
     * @date 2022/4/29
     */
    public boolean setWay(int x, int y) {
        if (map[6][5] == 2) {
            return true;
        } else {
            if (map[x][y] == 0) {
                // 这个点还没走 就按照策略
                map[x][y] = 2;
                if (setWay(x + 1, y)) {// 下
                    return true;
                } else if (setWay(x, y + 1)) {// 右
                    return true;
                } else if (setWay(x - 1, y)) {// 左
                    return true;
                } else if (setWay(x, y - 1)) {// 上
                    return true;
                } else {
                    map[x][y] = 3;// 该点走不通
                    return false;
                }
            } else {
                return false;
            }
        }
    }

    /**
     * 策略：右 下 上 左，走不通再回溯
     */
    public boolean setWay2(int x, int y) {
        if (map[6][5] == 2) {
            return true;
        } else {
            if (map[x][y] == 0) {
                // 这个点还没走 就按照策略
                map[x][y] = 2;
                if (setWay2(x, y + 1)) {// 右
                    return true;
                } else if (setWay2(x + 1, y)) {// 下
                    return true;
                } else if (setWay2(x - 1, y)) {// 左
                    return true;
                } else if (setWay2(x, y - 1)) {// 上
                    return true;
                } else {
                    map[x][y] = 3;// 该点走不通
                    return false;
                }
            } else {
                return false;
            }
        }
    }


    public void show() {
        for (int[] ints : map) {
            for (int anInt : ints) {
                if (anInt == 1) {
                    System.out.print("* ");
                } else if (anInt == 3) {
                    System.out.print("x ");
                } else if (anInt == 2) {
                    System.out.print("√ ");
                } else {
                    System.out.print(anInt + " ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

}
